package stu.day47;

public class hw2 {
    public String longestPalindrome(String s) {

       int len = s.length();
       int[][] dp = new int[len][len];

       for(int i=0;i<len;i++){
           dp[i][i] = 1;
       }

       for (int i=len-1;i>=0;i--){
           for (int j=i+1;j<len;j++){

               if(s.charAt(i)==s.charAt(j)){
                   if(j-i==1){
                       dp[i][j] = 1;
                   }else {
                       dp[i][j] = dp[i+1][j-1];
                   }
               }
           }
       }

       int left = 0;
       int right = 0;
       int max = 0;

        for (int i=0;i<len;i++){
            for (int j=i;j<len;j++){

                if(dp[i][j]==1){
                   if(j-i+1>max){
                       max = j-i+1;
                       left = i;
                       right = j+1;
                   }
                }
            }
        }

        return s.substring(left,right);

    }
}
